#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>

#define N 10005
#define M 200
#define MAX 2100000000
#define MIN -2100000000

using namespace std;

struct node{
    int key;
    int index;
    int degree;
    bool mark;
    node *p, *child, *left, *right;
};

struct heap{
    node *min;
    int n;
};

node *a[M];

void print_all_root(heap *h){
    printf("Print all roots: ");
    if (h->min != NULL){
        node *itr = h->min;
        do{
            printf("%d(%d) ", itr->key, itr->degree);
            itr = itr->right;
        }while(itr != h->min);
    } else {
        printf("NULL");
    }
    printf("\n");
}

void create_list(node *x){
    x->left = x;
    x->right = x;
}

// make x as a sibling of y.
void insert_list(node *y, node *x){
    if (y==NULL){
        printf("[ERROR] y is NULL!!!\n");
        return;
    }
    x->right = y->right;
    x->left = y;
    x->left->right = x;
    x->right->left = x;
}

void fib_heap_insert(heap *h, node *x){
    x->degree = 0;
    x->p = x->child = NULL;
    x->mark = false;
    if (h->min == NULL) {
        // create a root list for h containing just x.
        create_list(x);
        h->min = x;
    } else {
        // insert x into h's root list.
        insert_list(h->min, x);
        if (x->key < h->min->key){
            h->min = x;
        }
    }
    h->n = h->n + 1;
}

void make_fib_heap(heap *h){
    h->n = 0;
    h->min = NULL;
}

node *fib_minimum(heap *h){
    return h->min;
}

void fib_heap_link(heap *h, node *y, node *x){
    // remove y from the root list of h.
    /*
    if (y != y->right) {
        y->right->left = y->left;
        y->left->right = y->right;
    }
    */
    // make y a child of x, incrementing x.degree.
    y->p = x;
    if (x->child == NULL){
        x->child = y;
        create_list(y);
    } else {
        insert_list(x->child, y);
    }
    x->degree = x->degree +1;
    y->mark = false;
}

void consolidate(heap *h){
    int maxx = 0;
    a[0] = NULL;
    for(node *w = h->min;;){
        node *next_w = w->right;
        node *x = w;
        int d = x->degree;
        while (d <= maxx && a[d] != NULL) {
            node *y = a[d];
            if (x->key > y->key) {
                node *temp = x;
                x = y;
                y = temp;
            }
            fib_heap_link(h, y, x);
            a[d] = NULL;
            d = d+1;
        }
        while(maxx < d) 
            a[++maxx] = NULL;
        a[d] = x;
        w=next_w;
        if (w == h->min) break;
    }
    h->min = NULL;
    for(int i = 0; i <= maxx;i++){
        if (a[i] == NULL)
            continue;
        if (h->min == NULL) {
            create_list(a[i]);
            h->min = a[i];
        } else {
            insert_list(h->min, a[i]);
            a[i]->p = NULL;
            if (a[i]->key < h->min->key)
                h->min = a[i];
        }            
    }
}

node* fib_heap_extract_min(heap *h){
    node *z = h->min;
    if (z!= NULL){
        if (z->child != NULL){
            node *x = z->child;
            do{
                node *next_x= x->right;
                // add x to the root list of h.
                insert_list(h->min, x);
                x->p = NULL;
                x = next_x;
            }while(x != z->child);
        }
        // remove z from the root list of h.
        z->left->right = z->right;
        z->right->left = z->left;
        if (z == z->right){ // only one child.
            h->min = NULL;
        } else {
            h->min = z->right;
            consolidate(h);
        }
        h->n = h->n -1;
    }
    return z;
}

void cut(heap *h, node *x, node *y){
    // remove x from the child list of y, decrementing y.degree.
    if (x == x->right){ // only one child.
        y->child = NULL;
    } else {
        y->child = x->right;
        x->right->left = x->left;
        x->left->right = x->right;
    }
    y->degree = y->degree -1;
    insert_list(h->min, x);
    x->p = NULL;
    x->mark = false;
}

void cascading_cut(heap *h, node *y){
    if (y->p == NULL)
        return;
    if (y->mark == false) {
        y->mark = true;
    } else {
        node *z = y->p;
        cut(h, y, z);
        cascading_cut(h, z);
    }
}

void fib_heap_decrease_key(heap *h, node *x, int k){
    if (k > x->key){
        printf("[ERROR] new key is greater than current key.\n");
        return;
    }
    x->key = k;
    node *y = x->p;
    if (y != NULL && x->key < y->key){
        cut(h, x, y);
        cascading_cut(h, y);
    }
    if (x->key < h->min->key){
        h->min = x;
    }
}

heap h;
node nodes[N];
int visit[N];
int n,m;
vector<pair<int, int> > arr[N];
int main(){
    int tc;
    scanf("%d", &tc);
    for(int tcc = tc; tcc>0; tcc--){
        int size = 0;
        scanf("%d %d",&n,&m);
        for(int i =0; i < n;i++) {
            arr[i].clear();
            visit[i] = 0;
        }
        
        for(int i = 0; i < m;i++){
            int j,k,l;
            scanf("%d %d %d", &j,&k,&l);
            arr[j].push_back(make_pair(k,l));
            arr[k].push_back(make_pair(j,l));
        }
        
        node u;
        make_fib_heap(&h); 
        for(int i = 0; i <n;i++){
            u.key = MAX;
            u.index = i;
            nodes[size++] = u;
            fib_heap_insert(&h, &nodes[size-1]);
        }
        fib_heap_decrease_key(&h, &nodes[0], 0);
        int answer = -1;
        while(1){
            
            node *v = fib_heap_extract_min(&h);
            visit[v->index] = 1;
            if (v->index == n-1){
                answer = v->key;
                break;
            }
            int ind = v->index;
            for(int i = 0; i <arr[ind].size(); i++){
                if (visit[arr[ind][i].first] == 1)
                    continue;
                if (nodes[arr[ind][i].first].key > v->key + arr[ind][i].second){
                    fib_heap_decrease_key(&h,
                            &nodes[arr[ind][i].first],
                            v->key + arr[ind][i].second);
                }
            }
        }
        printf("%d\n", answer);
    }
    return 0;
}
